/**
 * 判断是不是平衡二叉树
 *
 * 描述
 * 输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 * 平衡二叉树（Balanced Binary Tree），具有以下性质：它是一
 * 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个
 * 子树都是一棵平衡二叉树。
 * 样例解释：
 * 样例二叉树如图，为一颗平衡二叉树
 * 注：我们约定空树是平衡二叉树。
 *
 * 数据范围：
 * n≤100,树上节点的val值满足0≤n≤1000
 *
 * 要求：
 * 空间复杂度O(1)，
 * 时间复杂度O(n)
 *
 * 输入描述：
 * 输入一棵二叉树的根节点
 *
 * 返回值描述：
 * 输出一个布尔类型的值
 */

/**
 * 方法 1 :
 * 自上而下的方法, 很明显这个算法时间和空间复杂度都会太过于大了
 * 但是我还是解释一下吧, 首先就是要确定是否是平衡二叉树有两个条件
 * 就是left, right 子树都要是平衡二叉树, 其次是left, right
 * 高度差要不大于 1, 就是这两个条件, 所以我们先求出两边的高度,
 * 然后再用高度进行第一波判断, 再来就是判断两个子树了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 *
 * 方法 2 :
 * 我们要对上面的算法进行优化的话, 其实就是要把子上而下的方法改为子下而上的,
 * 在我们求高度的同时进行平衡二叉树的判断, 这就让我们苦恼了, 是否为平衡二叉
 * 树返回的是 boolean, 但是高度返回却是 int, 那我们就要想办法处理这个问题
 * 我们将不是平衡二叉树的返回 -1, 是的返回正常的 int值
 *
 */

public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类 
     * @return bool布尔型
     */
    public boolean IsBalanced_Solution1 (TreeNode pRoot) {
        // write code here

        // 为空直接返回 true
        if (pRoot == null) {
            return true;
        }

        // 左右子树的高度
        int left = getHeight1(pRoot.left);
        int right = getHeight1(pRoot.right);

        // 高度差大于 1, 返回 false
        if (right - left > 1 || left - right > 1) {
            return false;
        }

        // 然后就是两边的子树都要是平衡二叉树
        return IsBalanced_Solution1(pRoot.left) && IsBalanced_Solution1(pRoot.right);
    }

    // 求节点的高度
    public int getHeight1(TreeNode root) {

        // 出口
        if (root == null) {
            return 0;
        }


        // 左右高度
        int left = getHeight1(root.left) + 1;
        int right = getHeight1(root.right) + 1;

        // 返回最大的一个
        return Math.max(left, right);
    }


    // *******************************************************************
    // 2.
    public boolean IsBalanced_Solution (TreeNode pRoot) {
        // write code here

        // 不为 -1 就是平衡二叉树
        return getHeight(pRoot) != -1;
    }

    // 是平衡二叉树返回正常 int值
    // 不是返回 -1
    // 也就是这个函数既有返回高度的功能也有判断是否为平衡二叉树的功能
    public int getHeight(TreeNode root) {

        // 出口
        if (root == null) {
            return 0;
        }

        // 左边的高度
        int left = getHeight(root.left);

        // 剪枝
        if (left == -1) {
            return -1;
        }

        // 右边的高度
        int right = getHeight(root.right);

        // 剪枝
        if (right == -1) {
            return -1;
        }

        return Math.abs(left - right) <= 1 ? Math.max(left, right) + 1 : -1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
